\subsection{Network Coding}
\label{prestudy:errororrectingcodes:networkcoding}
\acf{NC} is an extra layer of coding applied between source coding and channel coding, and is used to enhance either data transmission through an unreliable data channel, or throughput in routing, when using a reliable data channel. The type of \ac{NC} in focus is \ac{RLNC}, due to the simple approach to encoding and decoding of data. \cite{NCBASICS}

\subsubsection{Random Linear Network Coding}
Using \ac{RLNC}, the source node transmits network coded data instead of the original source data. The network coded packets $\{ \mathbf{p_1}, \mathbf{p_2}, ..., \mathbf{p_n}\}$ are random linear combinations of a series of source packets $\{\mathbf{x_1}, \mathbf{x_2}, ..., \mathbf{x_n}\}$. Because of this, a network coded packet $\mathbf{p_i}$ is a linear combination of the form $c_1\cdot \mathbf{x_1}+c_2\cdot \mathbf{x_2}+...+c_n\cdot \mathbf{x_n}$, where the vector of coding coefficients $\{c_1,c_2,...,c_n\}$ is denoted as the \textit{coding vector}.

If n source packets are present, at least n coded packets are generated. Because of the coding vectors being randomly generated, every coded packet is most likely unique for larger generation sizes. Equation \eqref{eq:nc-packet-coding} shows the matrix equation for coding the source packets.

%Matricer som viser hvordan man koder pakker
\begin{align} & %\label{eq:nc-packet-coding}
\left[
\begin{array}{c}	
\mathbf{p_{1}} \\
\mathbf{p_{2}} \\
\vdots \\
\mathbf{p_{m}}
\end{array}
\right]
=
\left[
\begin{array}{cccc}	
c_{11} & c_{12} & \cdots & c_{1g} \\
c_{21} & c_{22} & \cdots & c_{2g} \\
\vdots & \vdots & \ddots & \vdots \\
c_{m1} & c_{m2} & \cdots & c_{mg}
\end{array}
\right]
\left[
\begin{array}{c}	
\mathbf{x_{1}} \\
\mathbf{x_{2}} \\
\vdots \\
\mathbf{x_{g}}
\end{array}
\right]
\label{eq:nc-packet-coding}
\intertext{Where:}
&\text{g is the number of source packets, also known as generation size} \notag\\
&\text{$\mathbf{x_i}$ are the source packets} \notag\\
&\text{$c_{ij}$ are the coding coefficients $\in \mathbb{F}_{2^m}$} \notag\\
&\text{$\mathbf{p_i}$ are the resulting network coded packets} \notag\\
&\text{$\mathbf{m}$ is the number of generated packets} \notag\\
&\text{$m\geq g$ to allow receivers to decode}\notag
\end{align}

The coding coefficients are generated over a finite field, $\mathbb{F}_q$, where $q$ denotes the field size e.g. the binary field: $\mathbb{F}_2  = \{0,1\}$. Using the binary field, which is the simplest case, the coding process will simply XOR the packets included by the coding coefficients.

Encoded packets are sent in sets called \textit{generations}. The size of a generation, denoted \textit{g}, can be fixed or dynamical depending on the application. 
For the sink to be able to decode a generation it has to have received \textit{g} linearly independent encoded packets. Even for a small field like the binary, the probability of generating a packet useful to the sink is high. A property of \ac{RLNC} which is further investigated in Section \ref{sec:eep}. This means that successful decoding does not depend on the order and uniqueness of the received packets, as they do in both unicast and $"$naive$"$ broadcast described in Section \ref{prestudy:identifyproblemandscenario:network}.
This property of \ac{NC} is significant when broadcasting data to multiple nodes, because the source node does not need to know what packets the individual nodes needs transmitted, as in traditional uni- and broadcast without \ac{NC}. 


% !! This shall be moved to comparison !!


\subsubsection{Comparison to Naive Broadcast}
In Figure \ref{fig:nc-vs-naive} naive broadcast and \ac{RLNC} is compared. A scenario like that in Figure \ref{fig:introductory:initial} shall be considered where there are 10 nodes, 100 source packets and a uniform probability of transmission error equal to 10 \% for all the nodes. The graph shows the number of packets needed to be transmitted to achieve a certain probability that all 10 sinks have received the generation of 100 source packets. As described, \ac{NC} removes the need for unique packets and instead relies on receiving linearly independent combinations. By using a very high field size, the probability of linear dependency becomes arbitrarily small. Equation \eqref{eq:nc_1node} assumes an infinite field size. The consequences of this assumption is discussed in Section \ref{sec:eep}, but it has little influence on the result. This means that it is sufficient to receive 100 packets in total, although this is a simplified approach.

The analytical evaluation of \ac{NC} is twofold. Equation \eqref{eq:nc_1node} calculates the probability of $k$ successes in $n$ trials with probability of success in one trial equal to $p$. Equation \eqref{eq:nc_nnodes} extends \eqref{eq:nc_1node} by requiring at least $m$ successes out of $t$ transmissions and finally calculates the probability of this happening to all $j$ nodes.

%% Fixing NC formulas
\begin{align}
P(n,k,p)&=\binom{n}{k}\cdot p^k\cdot (1-p)^{n-k}\label{eq:nc_1node}
\intertext{Where:}
n&\text{ is the total number of transmissions}\notag\\
k&\text{ is the number of received packets from $n$ transmissions}\nonumber\\
p&\text{ is the probability of successful transmission}\notag
\intertext{Which can be extended to:}
P_A&=\left(\sum_{k=m}^{t}P(t,k,p)\right) ^j \label{eq:nc_nnodes}
\intertext{Where:}
P_A&\text{ is the probability that all nodes got at least $m$ packets}\notag\\
m&\text{ is the minimum number of packets needed}\notag\\
j&\text{ is the number of nodes}\notag\\
t&\text{ is the total number of transmitted packets}\notag
\end{align}
%% End fixing NC formula

\begin{figure}[h!]
\centering
\includegraphics[width=1\textwidth]{figs/netcod_plot.eps}
\caption{Comparison of \ac{RLNC} and naive broadcast with retransmissions in order to ensure reliability with a certain probability.}
\label{fig:nc-vs-naive}
\end{figure}

The comparison shows that \ac{RLNC} requires a lot less bandwidth than naive broadcast to achieve equal reliability statistics. The inferior performance of naive broadcast is due to the need to retransmit unique source packets for one or more node to recover from packet loss. 

\subsubsection{Protection of Data}
In Section \ref{prestudy:identifyproblemandscenario:video} concerning video streaming, it is found that some data in a video stream can be regarded as being of higher importance. \ac{NC} can be used to protect this data. By including the important data in the linear combinations more often than the rest of the data, thus transmitting more information about that particular data. This approach of prioritizing some data is often referred to as \acf{UEP} as opposed to \acf{EEP}.

Mechanisms of \ac{UEP} applied to \ac{NC} have been considered in a number of research papers \cite{UEP_RLC_MC}. Even though theoretical results are promising, actual implementations of \ac{NC} with \ac{UEP} seem limited\footnote{None of the authors of this report could find any open  practical implementations.}. The general idea behind \ac{UEP} applied to \ac{NC} is that receivers not being able to collect a whole generation of encoded packets due to bad link quality, at least should be able to recover the most import data of that specific generation.





%there has not been any practical implementations of network coding with \ac{UEP}.

%For sinks with bad link quality network coding without \ac{UEP} will not be optimal because of the fact that sinks need a specific number of packets to decode the data. If a sink does not receive the necessary packets in a generation the video stream will potentially miss an I-frame or all frames for a period of time and the user experience will decrease. 


%% OLD SHIT
%\begin{align}
%P_{\mathrm{nc}}&=\left[\binom{t}{x}\cdot p^{x}\cdot(1-p)^{t-x}\right]^{n} \label{eq:broadcastncpmf}
%\intertext{Where:}
%P_{\mathrm{nc}}&\text{ is the probability of all nodes being able to decode the original data}\notag\\
%x&\text{ is the number of source packets to each node}\notag\\
%n&\text{ is the number of nodes} \notag\\
%t&\text{ is the number of transmissions} \notag\\
%p&\text{ is the probability that a node receives the transmitted packet} \notag
%\end{align}


%When the source needs to send data instead of the original source data, a series of coded packets are generated at the source node and sent instead. These coded packets, $\{p_1, p_2, ..., p_n\}$, are, using \ac{RLNC}, random linear combinations of a series of source packets, $\{x_1, x_2, ..., x_n\}$ . A coded packet is therefore on the form $c_1\cdot x_1+c_2\cdot x_2+...+c_n\cdot x_n$, where the coding coefficients $\{c_1,c_2,...,c_n\}$ assembled in a vector is called the \textit{coding vector}. 

